package com.leetcode.array;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
 * <p>
 * 以任意顺序返回这两个数字均可。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [1]
 * 输出: [2,3]
 * 示例 2:
 * <p>
 * 输入: [2,3]
 * 输出: [1,4]
 * 提示：
 * <p>
 * nums.length <= 30000
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/missing-two-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class D_missingTwo {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 2};
        int[] ints1 = missingTwo(nums);
        System.out.printf(ints1[0] + " : " + ints1[1]);
    }

    public static int[] missingTwo(int[] nums) {
        // 1、hashmap
        // return hashmap(nums);

        // 2、位运算
        int n = nums.length + 2;

        int xorSum = 0;

        for (int num : nums) {
            xorSum ^= num;
        }

        for (int i = 1; i <= n; i++) {
            xorSum ^= i;
        }
        // 最低位为1的 所在位置
        int lsp = xorSum & (-xorSum);

        // 跟lsp与运算，区分出两大类数据，做与或，从而得出missing的数据
        int type1 = 0, type2 = 0;
        for (int num : nums) {
            if ((num & lsp) != 0) {
                type1 ^= num;
            } else {
                type2 ^= num;
            }
        }

        for (int i = 1; i <= n; i++) {
            if ((i & lsp) != 0) {
                type1 ^= i;
            } else {
                type2 ^= i;
            }
        }

        return new int[]{type1, type2};

    }

    private static int[] hashmap(int[] nums) {
        int[] twoMiss = new int[]{-1, -1};
        int n = nums.length + 2;
        Map<Integer, Integer> map = new HashMap<>(n);
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], 1);
        }
        for (int i = 1; i <= n; i++) {
            if (map.get(i) == null) {
                if (twoMiss[0] == -1) {
                    twoMiss[0] = i;
                } else {
                    twoMiss[1] = i;
                }
            }
        }
        return twoMiss;
    }
}
